//堆排序
const arr = [11, 8, 3, 9, 7, 1, 2, 5];

// 建堆
function buildHeap(arr) {
  for (let i = parseInt(arr.length / 2); i >= 1; i--) {
    heapify(arr, i, arr.length-1);
  }
}

// 堆化 从上向下堆化
function heapify(arr, i, n) {
  let mPos = i;
  while (true) {
    if (i * 2 < n && arr[i] < arr[2 * i]) {
      mPos = 2 * i;
    }
    if (2 * i + 1 < n && arr[i] < arr[2 * i + 1]) {
      mPos = 2 * i + 1;
    }
    if (mPos === i) {
      break;
    }
    swap(arr, i, mPos);
    i = mPos;
  }
}

function swap(arr, i, j) {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}
console.log(arr);
